#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
using LL = long long;
int n, m;
const int mod = 1e9 + 7;
int f[7][7];
int v[7][7] = {
    {0, 0, 0, 0, 0, 0, 0},
    {0, 4, 4, 4, 4, 4, 4}};

int rev(int a)
{
    if (a > 3)
        return a - 3;
    else
        return a + 3;
}

void print(int a[][7])
{
    for (int i = 1; i <= 6; ++i)
    {
        for (int j = 1; j <= 6; ++j)
            cout << a[i][j] << ' ';
        puts("");
    }
}

void mul(int a[][7], int f[][7])
{
    int c[7][7] = {0};
    for (int i = 1; i <= 6; ++i)
        for (int j = 1; j <= 6; ++j)
            for (int k = 1; k <= 6; ++k)
                c[i][j] = (c[i][j] + (LL)a[i][k] * f[k][j] % mod) % mod;
    memcpy(a, c, sizeof c);
}

int get()
{
    if (n == 0)
        return 0;
    n -= 1;
    while (n)
    {
        if (n & 1)
            mul(v, f);
        mul(f, f);
        n >>= 1;
    }
    LL res = 0;
    for (int i = 1; i <= 6; ++i)
        res = (res + v[1][i]) % mod;
    return res;
}

int main()
{

    cin >> n >> m;
    while (m--)
    {
        int a, b;
        cin >> a >> b;
        f[a][rev(b)] = 1;
        f[b][rev(a)] = 1;
    }
    for (int i = 1; i <= 6; ++i)
        for (int j = 1; j <= 6; ++j)
            f[i][j] = f[i][j] == 0 ? 4 : 0;
    // print(f);
    cout << get() << endl;
}